0655. 输出二叉树【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 递归

1. 📝 题目描述

• leetcode

给你一棵二叉树的根节点 root，请你构造一个下标从 0 开始、大小为 m x n 的字符串矩阵 res，用以表示树的 格式化布局。构造此格式化布局矩阵需要遵循以下规则：

• 树的 高度 为 height，矩阵的行数 m 应该等于 height + 1。
• 矩阵的列数 n 应该等于 2^height+1 - 1。
• 根节点 需要放置在 顶行 的 正中间，对应位置为 res[0][(n-1)/2]。
• 对于放置在矩阵中的每个节点，设对应位置为 res[r][c]，将其左子节点放置在 res[r+1][c-2^height-r-1]，右子节点放置在 res[r+1][c+2^height-r-1]。
• 继续这一过程，直到树中的所有节点都妥善放置。
• 任意空单元格都应该包含空字符串 ""。

返回构造得到的矩阵 res。

---

示例 1：

输入：root = [1,2]
输出：
[["","1",""],
 ["2","",""]]

示例 2：

输入：root = [1,2,3,null,4]
输出：
[["","","","1","","",""],
 ["","2","","","","3",""],
 ["","","4","","","",""]]

---

提示：

• 树中节点数在范围 [1, 2^10] 内
• -99 <= Node.val <= 99
• 树的深度在范围 [1, 10] 内

2. 🎯 s.1 - 递归

c

int getHeight(struct TreeNode* node) {
    if (!node) return 0;
    int l = getHeight(node->left), r = getHeight(node->right);
    return 1 + (l > r ? l : r);
}

void fill(struct TreeNode* node, char*** res, int r, int c, int h) {
    if (!node) return;
    sprintf(res[r][c], "%d", node->val);
    int offset = 1 << (h - r - 2);
    fill(node->left, res, r + 1, c - offset, h);
    fill(node->right, res, r + 1, c + offset, h);
}

char*** printTree(struct TreeNode* root, int* returnSize, int** returnColumnSizes) {
    int h = getHeight(root);
    int n = (1 << h) - 1;
    char*** res = (char***)malloc(sizeof(char**) * h);
    *returnColumnSizes = (int*)malloc(sizeof(int) * h);
    for (int i = 0; i < h; i++) {
        res[i] = (char**)malloc(sizeof(char*) * n);
        (*returnColumnSizes)[i] = n;
        for (int j = 0; j < n; j++) {
            res[i][j] = (char*)calloc(12, 1);
        }
    }
    fill(root, res, 0, (n - 1) / 2, h);
    *returnSize = h;
    return res;
}

js

/**
 * @param {TreeNode} root
 * @return {string[][]}
 */
var printTree = function (root) {
  const getHeight = (node) =>
    !node ? 0 : 1 + Math.max(getHeight(node.left), getHeight(node.right))
  const h = getHeight(root)
  const n = (1 << h) - 1
  const res = Array.from({ length: h }, () => new Array(n).fill(''))
  const fill = (node, r, c) => {
    if (!node) return
    res[r][c] = '' + node.val
    const offset = 1 << (h - r - 2)
    fill(node.left, r + 1, c - offset)
    fill(node.right, r + 1, c + offset)
  }
  fill(root, 0, (n - 1) >> 1)
  return res
}

py

class Solution:
    def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:
        def height(node):
            if not node:
                return 0
            return 1 + max(height(node.left), height(node.right))
        h = height(root)
        n = (1 << h) - 1
        res = [[''] * n for _ in range(h)]
        def fill(node, r, c):
            if not node:
                return
            res[r][c] = str(node.val)
            offset = 1 << (h - r - 2)
            fill(node.left, r + 1, c - offset)
            fill(node.right, r + 1, c + offset)
        fill(root, 0, (n - 1) // 2)
        return res

• 时间复杂度：$O(h\times 2^h)$，其中 h 是树的高度
• 空间复杂度：$O(h\times 2^h)$，结果矩阵大小

算法思路：

• 先求树的高度 h，创建 h 行 (2^h - 1) 列的矩阵
• 根节点放在中间列，左右子节点偏移 $2^{h-r-2}$，递归填充